import java.util.ArrayList;
import java.util.List;

//找到字符串中所有字母异位词
//测试链接 https://leetcode.cn/problems/find-all-anagrams-in-a-string/description/
public class FindAnagrams {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> ans = new ArrayList<>();//存放答案
        int lens = s.length(), lenp = p.length();//字符串长度
        if(lenp > lens){ //特殊情况
            return ans;
        }

        int[] target = new int[26]; //存放p字符串中，每个字符出现的次数
        for(int i = 0; i < lenp; i++){
            target[p.charAt(i) - 'a'] ++;
        }

        int[] cur = new int[26];  //存放s字符串的子数组，每个字符出现的次数
        int countCur = 0; //记录cur数组存放的有效个数
        for(int left = 0, right = 0; right < lens; right++){
            int index = s.charAt(right) - 'a';

            cur[index]++;  //进窗口
            if(cur[index] <= target[index]){
                countCur++;
            };

            while(right - left + 1 > lenp){ //出窗口
                int index2 = s.charAt(left) - 'a';

                cur[index2]--;
                if(cur[index2] < target[index2]){
                    countCur--;
                }
                left++;
            }

            if(countCur ==lenp){ //更新结果
                ans.add(left);
            }

        }

        return ans;
    }
}
